//
//  Problem39.swift
//  TestProject 39. 组合总和
//
//  Created by 武侠 on 2020/8/25.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 39. 组合总和
 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 candidates 中的数字可以无限制重复被选取。

 说明：
 所有数字（包括 target）都是正整数。
 解集不能包含重复的组合。
 
 示例 1：
 输入：candidates = [2,3,6,7], target = 7,
 所求解集为：
 [
   [7],
   [2,2,3]
 ]
 
 示例 2：
 输入：candidates = [2,3,5], target = 8,
 所求解集为：
 [
   [2,2,2,2],
   [2,3,3],
   [3,5]
 ]
  
 提示：
 1 <= candidates.length <= 30
 1 <= candidates[i] <= 200
 candidate 中的每个元素都是独一无二的。
 1 <= target <= 500
 */
@objcMembers class Problem39: NSObject {
    func solution() {
        print(combinationSum([2,3,5], 2))
    }
    
    // 解题思路：回溯法，采用树结构
    //
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        if candidates.count == 0 {
            return []
        }
        
        var lists:[[Int]] = []
        var path:[Int] = []

        combinaNext(candidates.sorted(), 0, target, &path, &lists)
        return lists
    }
    
    func combinaNext(_ candidates:[Int], _ beigin: Int, _ target: Int, _ path: inout [Int], _ lists: inout[[Int]]) {
        
        if target < 0 {         // 不合适，放弃这颗枝
            return
        }
        if target == 0 {        // 找到目前，path符合
            lists.append(path)
            return
        }
        
        
        for i in beigin..<candidates.count {
            if target - candidates[i] < 0 {     // 剪枝，因为不符合，放弃递归
                break
            }
            
            path.append(candidates[i])
            combinaNext(candidates, i + 1, target - candidates[i], &path, &lists)
            
            // 删除上一颗枝
            path.removeLast()
        }
    }
}
